package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func rotateRight(head *ListNode, k int) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	prevMap := make(map[*ListNode]*ListNode)
	size := 1
	n := head
	end := head
	for n.Next != nil {
		prevMap[n.Next] = n
		end = n.Next
		size++
		n = n.Next
	}
	result := head
	k = k % size
	for i := 0; i < k; i++ {
		end.Next = result
		result = end
		end = prevMap[end]
		end.Next = nil
	}
	return result
}

func main() {
	head := &ListNode{
		Val: 1,
		Next: &ListNode{
			Val: 2,
			Next: &ListNode{
				Val: 3,
				Next: &ListNode{
					Val: 4,
					Next: &ListNode{
						Val: 5,
					},
				},
			},
		},
	}
	r := rotateRight(head, 2)
	println(r)
}
